package com.jia.leetCode;

public class Pro0005 {
    public String longestPalindrome2(String s) {
    	if(null == s || s.length() == 0) return "";
    	int max  = 0;
    	String retStr = "";
        for(int i =0; i < s.length(); i++) {
        	for(int j = 0; j <= s.length(); j++) {
        		if(isPalindrome(s, i, j) && j - i + 1 >= max) {
        			max = j-i+1;
        			retStr = s.substring(i, j+1);
        		}
        	}
        }
        return retStr;
    }

	private boolean isPalindrome(String s, int i, int j) {
		while(i<j) {
			if(s.charAt(i) != s.charAt(j)) return false;
			i++;
			j--;
		}
		return true;
	}
	public String longestPalindrome(String s) {
		int len;
		if(s == null || (len = s.length()) < 2) return s;
		boolean[][] dp = new boolean[len][len];
		int[] ans = new int[2];
		int maxLen = 0;
		for(int i = 0; i < len; i++) {
			dp[i][i] = true;
		}
		for(int j = 1; j < len; j++) {
			for(int i = 0; i < j; i++) {

				if(s.charAt(i) == s.charAt(j)) {
					if(j - i > 2) {
						dp[i][j] = dp[i+1][j-1];
					}else {
						dp[i][j] = true;
					}
				}else{
					dp[i][j] = false;
				}
				if(dp[i][j] && j - i + 1 > maxLen) {
					ans[0] = i;
					ans[1] = j;
					maxLen = j - i + 1;
				}
			}
		}
		return s.substring(ans[0], ans[1] + 1);
	}
	public static void main(String[] args) {
		String s = "aaaa";
		Pro0005 pro0005 = new Pro0005();
		System.out.println(pro0005.longestPalindrome(s));
	}
}
